// ANSWER: 8.0540771484375
//
// v0 - simple brute force
// v1 - use compact data structure to store a folding state
// v2 - eliminate symmetry: no need to calculate reverse pattern
// v3 - eliminate symmetry: if the folding so far is a straight line, then no need
//      to grow toward both sides of the line.
//
// Implementation note: recursion is costly; reduce it where possible.
//

// Disable C4351: new behavior: elements of array 'array' will be default initialized
#pragma warning(disable: 4351)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include "timer.h"

// bitvalue -- a type that stores only 0 or 1.
typedef int bitvalue;

// Represents a protein sequence, such as HHPPHHHPHHPH.
class protein
{
	int _length;
	unsigned int _value;

public:
	protein(int length, unsigned int value) 
		: _length(length), _value(value) 
	{
		assert(length >= 0 && length <= sizeof(unsigned int)*8);
		assert(value <= (1U<<length)-1);
	}

	int length() const { return _length; }
	unsigned int value() const { return _value; }

	protein reverse() const 
	{
		unsigned int v = _value, r = 0;
		for (int k = 0; k < _length; k++)
		{
			r <<= 1;
			r |= (v & 1);
			v >>= 1;
		}
		return protein(_length, r);
	}

	bitvalue operator[] (int i) const 
	{
		assert(i >= 0 && i < _length);
		return (_value >> i) & 1; 
	}

	bool operator == (const protein &p) const
	{
		return (_length == p._length) && (_value == p._value);
	}

	bool operator <= (const protein &p) const
	{
		return (_length < p._length) || (_length==p._length && _value<=p._value);
	}

	friend std::ostream& operator << (std::ostream &os, const protein &p) 
	{
		for (int i = 0; i < p.length(); i++)
			os << (p[i]? 'H' : 'P');
		return os;
	}
};

// Represents the folding state of a protein.
class folding
{
	typedef unsigned short row_type;
	static const int row_size = 16;
	static const int row_mask = 0x0f;

	row_type _filled[row_size]; // 1 if the cell is filled with value
	row_type _value[row_size];  // 1 if the cell is H and the cell is filled

public:
	folding() : _filled(), _value() { }
	
	bool filled(int i, int j) const 
	{ 
		return (_filled[i&row_mask] >> (j&row_mask)) & 1; 
	}
	
	bitvalue value(int i, int j) const 
	{
		return (_value[i&row_mask] >> (j&row_mask)) & 1; 
	}

	void clear()
	{
		memset(_filled, 0, sizeof(_filled));
		memset(_value, 0, sizeof(_value));
	}

	void fill(int i, int j, bitvalue value)
	{
		assert(value==1 || value==0);
		_filled[i&row_mask] |= (1 << (j&row_mask));
		_value[i&row_mask] |= (value << (j&row_mask));
	}

	void unfill(int i, int j)
	{
		_filled[i&row_mask] &= ~(1 << (j&row_mask));
		_value[i&row_mask] &= ~(1 << (j&row_mask));
	}

	int count_neighbor(int i, int j) const
	{
		return value(i-1, j) + value(i+1, j) + value(i, j-1) + value(i, j+1);
	}

	bool row_empty(int i) const
	{
		return _filled[i&row_mask] == 0;
	}
};

#if 1
// p: the protein to fold
// k: number of elements already folded
// i: row index of the last-folded element
// j: column position of the last-folded element
// state: folding state
static int find_optimal_contact_points(protein p, int k, int i, int j, folding &state)
{
	assert(k >= 0 && k < p.length());

	// start condition
	if (k == 0)
	{
		if (p.length() <= 1)
		{
			return 0;
		}
		else
		{
			state.clear();
			state.fill(0, 0, p[0]);
			return find_optimal_contact_points(p, 1, 0, 0, state);
		}
	}

	// fold the next element
	bitvalue b = p[k];
	static const int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
	int m = -10000;
	for (int d = 0; d < 4; d++)
	{
		int ii = i + dir[d][0], jj = j + dir[d][1];
		if (!state.filled(ii, jj))
		{
			state.fill(ii, jj, b);
			int count = b? state.count_neighbor(ii, jj) : 0;
			if (k+1 < p.length())
			{
				count += find_optimal_contact_points(p, k+1, ii, jj, state);
			}
			state.unfill(ii, jj);
			if (count > m)
				m = count;
		}

		// 2nd element always fold to the right
		if (k == 1)
			break;
		// If the current folding is in a line, then no need to fold the last direction.
		if (d == 2 && state.row_empty(1) && state.row_empty(-1))
			break;
	}
	return m;
}
#else

// p: the protein to fold
// k: number of elements already folded
// i: row index of the last-folded element
// j: column position of the last-folded element
// state: folding state
// Use the A* algorithm.
static int find_optimal_contact_points(protein p, int k, int i, int j, folding &)
{
	// Use a vector to store nodes in the search tree.
	struct node_t
	{
		folding state;    // partial folding state
		unsigned short g; // number of contact points in the partial state
		unsigned short f; // f = evaluation function value = g + h, where
		                  // h = the upper bound of remaining number of
		                  // contact points
		node_t(folding parent_state)
		{
		}
	};
	std::vector<node_t> nodes;

	// Use a priority queue to store the nodes in order of the evaluation 
	// function. Since the queue operations involve many swap() operations,
	// we only store the index to the nodes to improve performance.
#if 0
	class nodecomparer
	{
		const std::vector<node_t> &_nodes;
	public:
		nodecomparer(const std::vector<node_t> &nodes) : _nodes(nodes) { }
		bool operator() (int i, int j) const
		{
			return _nodes[i].f < _nodes[j].f;
		}
	};
	nodecomparer cc(nodes);
	std::priority_queue<int, std::vector<int>, nodecomparer> pq(cc);
#else
	auto node_comparer = [&nodes](int i, int j) -> bool {
		return nodes[i].f < nodes[j].f;
	};
	std::priority_queue<int, std::vector<int>, decltype(node_comparer)> pq(node_comparer);
#endif

	// Initialize the search space.
	node_t parent;
	parent.state.clear();
	parent.state.fill(0, 0, p[0]);
	parent.g = 0;
	parent.f = 0;
	nodes.push_back(parent);
	pq.push(0);

	// Expand the search space
	while (!pq.empty())
	{
		// Remove the first partial folding in the priority queue.
		int k = pq.top();
		pq.pop();
		const folding &state = nodes[k].state;

		// If this partial folding is complete, then it's the optimal folding.
		int i = 1, j = 1;

		// Expand its children. 
		bitvalue b = p[k];
		static const int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
		for (int d = 0; d < 4; d++)
		{
			int ii = i + dir[d][0], jj = j + dir[d][1];
			if (nodes[k].state.filled(ii, jj))
				continue;

			folding state(nodes[k].state);
			state.fill(ii, jj ,b);
			int count = b? state.count_neighbor(ii, jj) : 0;
			node_t node;
			node.f = 1;
			node.g = 1;
			node.state = state;

			// Computes a heuristic value for the partial folding.
			int h = 1;

			// Pruning: if the upper-bound of the number of contact points in this
			// partial folding is below the currently optimal partial folding, then
			// no need to proceed on this way.

			// Insert the partial folding state into the priority queue.
			int k2 = 1;
			pg.push(node);

			// Eliminate certain symmetry...
			// 2nd element always fold to the right
			if (k == 1)
				break;
			// If the current folding is in a line, then no need to fold the last direction.
			if (d == 2 && state.row_empty(1) && state.row_empty(-1))
				break;
		}


		while (1)
		{
			// 

			

		}
	}

		/*
	// start condition
	if (k == 0)
	{
		if (p.length() <= 1)
		{
			return 0;
		}
		else
		{
			state.clear();
			state.fill(0, 0, p[0]);
			return find_optimal_contact_points(p, 1, 0, 0, state);
		}
	}

	// fold the next element
	bitvalue b = p[k];
	static const int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
	int m = -10000;
	for (int d = 0; d < 4; d++)
	{
		int ii = i + dir[d][0], jj = j + dir[d][1];
		if (!state.filled(ii, jj))
		{
			state.fill(ii, jj, b);
			int count = b? state.count_neighbor(ii, jj) : 0;
			if (k+1 < p.length())
			{
				count += find_optimal_contact_points(p, k+1, ii, jj, state);
			}
			state.unfill(ii, jj);
			if (count > m)
				m = count;
		}

		// 2nd element always fold to the right
		if (k == 1)
			break;
		// If the current folding is in a line, then no need to fold the last direction.
		if (d == 2 && state.row_empty(1) && state.row_empty(-1))
			break;
	}
	return m;
	*/
}
#endif

static int get_total_contact_points(int N)
{
	folding state;

	// 0=P, 1=H
	int total = 0;
	for (int pattern = 0; pattern < (1<<N); pattern++)
	{
		protein p(N, pattern);
		protein p2 = p.reverse();
		if (p <= p2)
		{
			int count = find_optimal_contact_points(p, 0, 0, 0, state);
			//std::cout << "Protein = " << p << ", Count = " << count << std::endl;
			total += (p == p2)? count : 2*count;
		}
	}
	return total;
}

void solve_problem_300()
{
	hr_timer t;
#if 1
	//for (int n = 1; n <= 15; n++)
	for (int n = 1; n <= 8; n++)
	//for (int n = 1; n <= 15; n++)
#else
	for (int n = 15; n <= 15; n++)
#endif
	{	
		t.start();
		int total = get_total_contact_points(n);
		double t1 = t.stop();
		std::cout << n << " " << total << " " << t1 << std::endl;
	}
}
